Ariana's Site

Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?

This challenge only gives us a server to connect to with the following interactions:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+  hi talented participants, welcome to the FERMAN cryptography task!  +
+  Solve the given equations and decrypt the encrypted flag! Enjoy!    +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

| Parameters generation is a bit time consuming, so please be patient :P
| Options: 
|	[P]rint encrypted flag 
|	[R]eveal the parameters 
|	[Q]uit
P
| encrypt(flag) = 48790321481981070334284834897002743904143367742567080121139875503627677163558938442363151365001170923856543352995009198916999044114034490190573783771904020525587752191210344256704686085230514048180152780013748635642271859330908866389413727451104623973255339543797167920503564005931662152602543251766255090842659435974220819895436577204154690210899973842334999175452720629152039181296261452873185143203984819655252786655755387428741502392505402920556814585424516239256655975181009
| Options: 
|	[P]rint encrypted flag 
|	[R]eveal the parameters 
|	[Q]uit
R
	e = 65537
	isPrime(p) = True
	isPrime(q) = True
	n = p * q
	(p - 582)**2 + (q - 25)**2 = 14631667335665376436840829964208352592651640426073578145070933715959789971380009994599228441748977871671891122780871174585035107716073801876075537824911946177667748022294940252232874085867015283835699627140037360866815484198487657307973080528934669763321149163146222720745301051643570903526702386861550873974220860941488324946388489501970762170927237645397125403189863229303743865435714328534902839262771017996292025035300502112811380090440713136701311095838411721435477641677265625
	m = bytes_to_long(flag)
	c = pow(m, e, n)
| Options: 
|	[P]rint encrypted flag 
|	[R]eveal the parameters 
|	[Q]uit

Clearly the goal here is to solve for and we are given a sum-of-two-squares expression. This can easily be solved by factoring in , more specifically, note that we have

hence we simply pair up the factors of as complex conjugates to determine possible values of , then check if they are prime. Do note that one needs to convert the ring back to otherwise sage's is_prime would attempt to factor in or .

Solution at solve.sage

Ferman